// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

// 此外，你可以假设该网格的四条边均被水包围。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/number-of-islands
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 深度优先

// 执行用时：
// 16 ms
// , 在所有 C++ 提交中击败了
// 71.52%
// 的用户
// 内存消耗：
// 9.2 MB
// , 在所有 C++ 提交中击败了
// 86.15%
// 的用户

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<list>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()<1){
            return 0;
        }
        int res = 0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(dfs(grid,i,j)){
                    res++;
                }
            }
        }
        return res;
    }
    bool dfs(vector<vector<char>>& grid,int x,int y){
        if(x>=grid.size() || x<0 || y<0 || y>=grid[0].size()){
            return false;
        }
        if(grid[x][y]=='1'){
            grid[x][y]='0';
            dfs(grid,x-1,y);
            dfs(grid,x+1,y);
            dfs(grid,x,y-1);
            dfs(grid,x,y+1);
            return true;
        }
        else{
            return false;
        }
    }
};